home *** CD-ROM | disk | FTP | other *** search
/ InterCD 2000 September / september_2000.iso / intercd / root / ^Linux / WindowMaker / wrlib / CrCmap.c < prev    next >
Encoding:
C/C++ Source or Header  |  2000-01-14  |  17.5 KB  |  525 lines
  1. /* $XConsortium: CrCmap.c,v 1.6 94/04/17 20:15:53 rws Exp $ */
  2.  
  3. /* 
  4.  
  5. Copyright (c) 1989  X Consortium
  6.  
  7. Permission is hereby granted, free of charge, to any person obtaining a copy
  8. of this software and associated documentation files (the "Software"), to deal
  9. in the Software without restriction, including without limitation the rights
  10. to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11. copies of the Software, and to permit persons to whom the Software is
  12. furnished to do so, subject to the following conditions:
  13.  
  14. The above copyright notice and this permission notice shall be included in
  15. all copies or substantial portions of the Software.
  16.  
  17. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18. IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19. FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  20. X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  21. AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  22. CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  23.  
  24. Except as contained in this notice, the name of the X Consortium shall not be
  25. used in advertising or otherwise to promote the sale, use or other dealings
  26. in this Software without prior written authorization from the X Consortium.
  27.  
  28. */
  29.  
  30. /*
  31.  * Author:  Donna Converse, MIT X Consortium
  32.  */
  33.  
  34. /*
  35.  * CreateCmap.c - given a standard colormap description, make the map.
  36.  */
  37.  
  38. #include <stdlib.h>
  39. #include <stdio.h>
  40. #include <X11/Xlib.h>
  41. #include <X11/Xutil.h>
  42.  
  43.  
  44. static int    ROmap();        /* allocate entire map Read Only */
  45. static Status    ROorRWcell();        /* allocate a cell, prefer Read Only */
  46. static Status    RWcell();        /* allocate a cell Read Write */
  47. static int    compare();        /* for quicksort */
  48. static Status     contiguous();        /* find contiguous sequence of cells */
  49. static void    free_cells();        /* frees resources before quitting */
  50. static Status    readonly_map();        /* create a map in a RO visual type */
  51. static Status    readwrite_map();    /* create a map in a RW visual type */
  52.  
  53. #define lowbit(x) ((x) & (~(x) + 1))
  54. #define TRUEMATCH(mult,max,mask) \
  55.     (colormap->max * colormap->mult <= vinfo->mask && \
  56.      lowbit(vinfo->mask) == colormap->mult)
  57.  
  58. /*
  59.  * To create any one colormap which is described by an XStandardColormap
  60.  * structure, use XmuCreateColormap().
  61.  *
  62.  * Return 0 on failure, non-zero on success.
  63.  * Resources created by this function are not made permanent.
  64.  * No argument error checking is provided.  Use at your own risk.
  65.  *
  66.  * All colormaps are created with read only allocations, with the exception
  67.  * of read only allocations of colors in the default map or otherwise
  68.  * which fail to return the expected pixel value, and these are individually 
  69.  * defined as read/write allocations.  This is done so that all the cells
  70.  * defined in the default map are contiguous, for use in image processing.
  71.  * This typically happens with White and Black in the default map.
  72.  *
  73.  * Colormaps of static visuals are considered to be successfully created if
  74.  * the map of the static visual matches the definition given in the
  75.  * standard colormap structure.
  76.  */
  77.    
  78. Status XmuCreateColormap(dpy, colormap)
  79.     Display        *dpy;        /* specifies the connection under 
  80.                      * which the map is created */
  81.     XStandardColormap    *colormap;    /* specifies the map to be created,
  82.                      * and returns, particularly if the
  83.                      * map is created as a subset of the
  84.                      * default colormap of the screen,
  85.                      * the base_pixel of the map.
  86.                      */
  87. {
  88.     XVisualInfo        vinfo_template;    /* template visual information */
  89.     XVisualInfo        *vinfo;        /* matching visual information */
  90.     XVisualInfo        *vpointer;    /* for freeing the entire list */
  91.     long        vinfo_mask;    /* specifies the visual mask value */
  92.     int         n;        /* number of matching visuals */
  93.     int            status;        
  94.  
  95.     vinfo_template.visualid = colormap->visualid;
  96.     vinfo_mask = VisualIDMask;
  97.     if ((vinfo = XGetVisualInfo(dpy, vinfo_mask, &vinfo_template, &n)) == NULL)
  98.     return 0;
  99.  
  100.     /* A visual id may be valid on multiple screens.  Also, there may 
  101.      * be multiple visuals with identical visual ids at different depths.  
  102.      * If the colormap is the Default Colormap, use the Default Visual.
  103.      * Otherwise, arbitrarily, use the deepest visual.
  104.      */
  105.     vpointer = vinfo;
  106.     if (n > 1)
  107.     {
  108.     register int    i;
  109.     register int    screen_number;
  110.     Bool         def_cmap;
  111.  
  112.     def_cmap = False;
  113.     for (screen_number = ScreenCount(dpy); --screen_number >= 0; )
  114.         if (colormap->colormap == DefaultColormap(dpy, screen_number)) {
  115.         def_cmap = True;
  116.         break;
  117.         }
  118.  
  119.     if (def_cmap) {
  120.         for (i=0; i < n; i++, vinfo++) {
  121.         if (vinfo->visual == DefaultVisual(dpy, screen_number))
  122.             break;
  123.         }
  124.     } else {
  125.         unsigned int    maxdepth = 0;
  126.         XVisualInfo        *v = vinfo;
  127.  
  128.         for (i=0; i < n; i++, vinfo++)
  129.         if (vinfo->depth > maxdepth) {
  130.             maxdepth = vinfo->depth;
  131.             v = vinfo;
  132.         }
  133.         vinfo = v;
  134.     }
  135.     }
  136.  
  137.     if (vinfo->class == PseudoColor || vinfo->class == DirectColor ||
  138.     vinfo->class == GrayScale)
  139.     status = readwrite_map(dpy, vinfo, colormap);
  140.     else if (vinfo->class == TrueColor)
  141.     status = TRUEMATCH(red_mult, red_max, red_mask) &&
  142.              TRUEMATCH(green_mult, green_max, green_mask) &&
  143.          TRUEMATCH(blue_mult, blue_max, blue_mask);
  144.     else 
  145.     status = readonly_map(dpy, vinfo, colormap);
  146.     
  147.     XFree((char *) vpointer);
  148.     return status;
  149. }
  150.  
  151. /****************************************************************************/
  152. static Status readwrite_map(dpy, vinfo, colormap)
  153.     Display        *dpy;
  154.     XVisualInfo        *vinfo;
  155.     XStandardColormap    *colormap;
  156. {
  157.     register unsigned long i, n;    /* index counters */
  158.     int            ncolors;    /* number of colors to be defined */
  159.     int            npixels;    /* number of pixels allocated R/W */
  160.     int            first_index;    /* first index of pixels to use */
  161.     int            remainder;    /* first index of remainder */
  162.     XColor        color;        /* the definition of a color */
  163.     unsigned long    *pixels;    /* array of colormap pixels */
  164.     unsigned long    delta;
  165.  
  166.     
  167.     /* Determine ncolors, the number of colors to be defined.
  168.      * Insure that 1 < ncolors <= the colormap size.
  169.      */
  170.     if (vinfo->class == DirectColor) {
  171.     ncolors = colormap->red_max;
  172.     if (colormap->green_max > ncolors)
  173.         ncolors = colormap->green_max;
  174.     if (colormap->blue_max > ncolors)
  175.         ncolors = colormap->blue_max;
  176.     ncolors++;
  177.     delta = lowbit(vinfo->red_mask) +
  178.             lowbit(vinfo->green_mask) +
  179.         lowbit(vinfo->blue_mask);
  180.     } else {
  181.     ncolors = colormap->red_max * colormap->red_mult +
  182.           colormap->green_max * colormap->green_mult +
  183.           colormap->blue_max * colormap->blue_mult + 1;
  184.     delta = 1;
  185.     }
  186.     if (ncolors <= 1 || ncolors > vinfo->colormap_size)    return 0;
  187.  
  188.     /* Allocate Read/Write as much of the colormap as we can possibly get.
  189.      * Then insure that the pixels we were allocated are given in 
  190.      * monotonically increasing order, using a quicksort.  Next, insure
  191.      * that our allocation includes a subset of contiguous pixels at least
  192.      * as long as the number of colors to be defined.  Now we know that 
  193.      * these conditions are met:
  194.      *    1) There are no free cells in the colormap.
  195.      *  2) We have a contiguous sequence of pixels, monotonically 
  196.      *     increasing, of length >= the number of colors requested.
  197.      *
  198.      * One cell at a time, we will free, compute the next color value, 
  199.      * then allocate read only.  This takes a long time.
  200.      * This is done to insure that cells are allocated read only in the
  201.      * contiguous order which we prefer.  If the server has a choice of
  202.      * cells to grant to an allocation request, the server may give us any
  203.      * cell, so that is why we do these slow gymnastics.
  204.      */
  205.  
  206.     if ((pixels = (unsigned long *) calloc((unsigned) vinfo->colormap_size,
  207.                       sizeof(unsigned long))) == NULL)
  208.     return 0;
  209.  
  210.     if ((npixels = ROmap(dpy, colormap->colormap, pixels,
  211.                vinfo->colormap_size, ncolors)) == 0) {
  212.     free((char *) pixels);
  213.     return 0;
  214.     }
  215.  
  216.     qsort((char *) pixels, npixels, sizeof(unsigned long), compare);
  217.  
  218.     if (!contiguous(pixels, npixels, ncolors, delta, &first_index, &remainder))
  219.     {
  220.     /* can't find enough contiguous cells, give up */
  221.     XFreeColors(dpy, colormap->colormap, pixels, npixels,
  222.             (unsigned long) 0);
  223.     free((char *) pixels);
  224.     return 0;
  225.     }
  226.     colormap->base_pixel = pixels[first_index];
  227.  
  228.     /* construct a gray map */
  229.     if (colormap->red_mult == 1 && colormap->green_mult == 1 &&
  230.     colormap->blue_mult == 1)
  231.     for (n=colormap->base_pixel, i=0; i < ncolors; i++, n += delta)
  232.     {
  233.         color.pixel = n;
  234.         color.blue = color.green = color.red =
  235.         (unsigned short) ((i * 65535) / (colormap->red_max +
  236.                          colormap->green_max +
  237.                          colormap->blue_max));
  238.  
  239.         if (! ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color,
  240.                  first_index + i))
  241.         return 0;
  242.     }
  243.  
  244.     /* construct a red ramp map */
  245.     else if (colormap->green_max == 0 && colormap->blue_max == 0)
  246.         for (n=colormap->base_pixel, i=0; i < ncolors; i++, n += delta)
  247.     {
  248.         color.pixel = n;
  249.         color.red = (unsigned short) ((i * 65535) / colormap->red_max);
  250.         color.green = color.blue = 0;
  251.  
  252.         if (! ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color,
  253.                  first_index + i))
  254.         return 0;
  255.     }
  256.  
  257.     /* construct a green ramp map */
  258.     else if (colormap->red_max == 0 && colormap->blue_max == 0)
  259.         for (n=colormap->base_pixel, i=0; i < ncolors; i++, n += delta)
  260.     {
  261.         color.pixel = n;
  262.         color.green = (unsigned short) ((i * 65535) / colormap->green_max);
  263.         color.red = color.blue = 0;
  264.  
  265.         if (! ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color,
  266.                  first_index + i))
  267.         return 0;
  268.     }
  269.  
  270.     /* construct a blue ramp map */
  271.     else if (colormap->red_max == 0 && colormap->green_max == 0)
  272.         for (n=colormap->base_pixel, i=0; i < ncolors; i++, n += delta)
  273.     {
  274.         color.pixel = n;
  275.         color.blue = (unsigned short) ((i * 65535) / colormap->blue_max);
  276.         color.red = color.green = 0;
  277.  
  278.         if (! ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color,
  279.                  first_index + i))
  280.         return 0;
  281.     }
  282.  
  283.     /* construct a standard red green blue cube map */
  284.     else
  285.     {
  286. #define calc(max,mult) (((n / colormap->mult) % \
  287.              (colormap->max + 1)) * 65535) / colormap->max
  288.  
  289.         for (n=0, i=0; i < ncolors; i++, n += delta)
  290.     {
  291.         color.pixel = n + colormap->base_pixel;
  292.         color.red = calc(red_max, red_mult);
  293.         color.green = calc(green_max, green_mult);
  294.         color.blue = calc(blue_max, blue_mult);
  295.         if (! ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color,
  296.                  first_index + i))
  297.         return 0;
  298.     }
  299. #undef calc
  300.     }
  301.     /* We have a read-only map defined.  Now free unused cells,
  302.      * first those occuring before the contiguous sequence begins,
  303.      * then any following the contiguous sequence.
  304.      */
  305.  
  306.     if (first_index)
  307.     XFreeColors(dpy, colormap->colormap, pixels, first_index, 
  308.             (unsigned long) 0);
  309.     if (remainder)
  310.     XFreeColors(dpy, colormap->colormap,
  311.             &(pixels[first_index + ncolors]), remainder,
  312.             (unsigned long) 0);
  313.  
  314.     free((char *) pixels);
  315.     return 1;
  316. }
  317.  
  318.  
  319. /****************************************************************************/
  320. static int ROmap(dpy, cmap, pixels, m, n)
  321.     Display        *dpy;        /* the X server connection */
  322.     Colormap        cmap;        /* specifies colormap ID */
  323.     unsigned long    pixels[];    /* returns pixel allocations */
  324.     int            m;        /* specifies colormap size */
  325.     int            n;        /* specifies number of colors */
  326. {
  327.     register int    p;
  328.  
  329.     /* first try to allocate the entire colormap */
  330.     if (XAllocColorCells(dpy, cmap, 1, (unsigned long *) NULL, 
  331.              (unsigned) 0, pixels, (unsigned) m))
  332.     return m;
  333.  
  334.     /* Allocate all available cells in the colormap, using a binary
  335.      * algorithm to discover how many cells we can allocate in the colormap.
  336.      */
  337.     m--;
  338.     while (n <= m) {
  339.     p = n + ((m - n + 1) / 2);
  340.     if (XAllocColorCells(dpy, cmap, 1, (unsigned long *) NULL,
  341.                  (unsigned) 0, pixels, (unsigned) p)) {
  342.         if (p == m)
  343.         return p;
  344.         else {
  345.         XFreeColors(dpy, cmap, pixels, p, (unsigned long) 0);
  346.         n = p;
  347.         }
  348.     }
  349.     else
  350.         m = p - 1;
  351.     }
  352.     return 0;
  353. }
  354.       
  355.  
  356. /****************************************************************************/
  357. static Status contiguous(pixels, npixels, ncolors, delta, first, rem)
  358.     unsigned long    pixels[];    /* specifies allocated pixels */
  359.     int            npixels;    /* specifies count of alloc'd pixels */
  360.     int            ncolors;    /* specifies needed sequence length */
  361.     unsigned long    delta;        /* between pixels */
  362.     int            *first;        /* returns first index of sequence */
  363.     int            *rem;        /* returns first index after sequence,
  364.                      * or 0, if none follow */
  365. {
  366.     register int i = 1;        /* walking index into the pixel array */
  367.     register int count = 1;    /* length of sequence discovered so far */
  368.  
  369.     *first = 0;
  370.     if (npixels == ncolors) {
  371.     *rem = 0;
  372.     return 1;
  373.     }
  374.     *rem = npixels - 1;
  375.     while (count < ncolors && ncolors - count <= *rem)
  376.     {
  377.     if (pixels[i-1] + delta == pixels[i])
  378.         count++;
  379.     else {
  380.         count = 1;
  381.         *first = i;
  382.     }
  383.     i++;
  384.     (*rem)--;
  385.     }
  386.     if (count != ncolors)
  387.     return 0;
  388.     return 1;
  389. }
  390.  
  391.  
  392. /****************************************************************************/
  393. static Status ROorRWcell(dpy, cmap, pixels, npixels, color, p)
  394.     Display        *dpy;
  395.     Colormap        cmap;
  396.     unsigned long    pixels[];
  397.     int            npixels;
  398.     XColor        *color;
  399.     unsigned long    p;
  400. {
  401.     unsigned long    pixel;
  402.     XColor        request;
  403.  
  404.     /* Free the read/write allocation of one cell in the colormap.
  405.      * Request a read only allocation of one cell in the colormap.
  406.      * If the read only allocation cannot be granted, give up, because
  407.      * there must be no free cells in the colormap.
  408.      * If the read only allocation is granted, but gives us a cell which
  409.      * is not the one that we just freed, it is probably the case that
  410.      * we are trying allocate White or Black or some other color which
  411.      * already has a read-only allocation in the map.  So we try to 
  412.      * allocate the previously freed cell with a read/write allocation,
  413.      * because we want contiguous cells for image processing algorithms.
  414.      */
  415.      
  416.     pixel = color->pixel;
  417.     request.red = color->red;
  418.     request.green = color->green;
  419.     request.blue = color->blue;
  420.  
  421.     XFreeColors(dpy, cmap, &pixel, 1, (unsigned long) 0);
  422.     if (! XAllocColor(dpy, cmap, color) 
  423.     || (color->pixel != pixel &&
  424.         (!RWcell(dpy, cmap, color, &request, &pixel)))) 
  425.     {
  426.     free_cells(dpy, cmap, pixels, npixels, (int)p);
  427.     return 0;
  428.     }
  429.     return 1;
  430. }
  431.  
  432.  
  433. /****************************************************************************/
  434. static void free_cells(dpy, cmap, pixels, npixels,  p)
  435.     Display        *dpy;
  436.     Colormap        cmap;
  437.     unsigned long    pixels[];    /* to be freed */
  438.     int            npixels;        /* original number allocated */
  439.     int            p;      
  440. {
  441.     /* One of the npixels allocated has already been freed.
  442.      * p is the index of the freed pixel.
  443.      * First free the pixels preceeding p, and there are p of them;
  444.      * then free the pixels following p, there are npixels - p - 1 of them.
  445.      */
  446.     XFreeColors(dpy, cmap, pixels, p, (unsigned long) 0);
  447.     XFreeColors(dpy, cmap, &(pixels[p+1]), npixels - p - 1, (unsigned long) 0);
  448.     free((char *) pixels);
  449. }
  450.  
  451.  
  452. /****************************************************************************/
  453. static Status RWcell(dpy, cmap, color, request, pixel)
  454.     Display        *dpy;
  455.     Colormap        cmap;
  456.     XColor        *color;
  457.     XColor        *request;
  458.     unsigned long    *pixel;
  459. {
  460.     unsigned long    n = *pixel;
  461.  
  462.     XFreeColors(dpy, cmap, &(color->pixel), 1, (unsigned long)0);
  463.     if (! XAllocColorCells(dpy, cmap, (Bool) 0, (unsigned long *) NULL,
  464.                (unsigned) 0, pixel, (unsigned) 1))
  465.     return 0;
  466.     if (*pixel != n)
  467.     {
  468.     XFreeColors(dpy, cmap, pixel, 1, (unsigned long) 0);
  469.     return 0;
  470.     }
  471.     color->pixel = *pixel;
  472.     color->flags = DoRed | DoGreen | DoBlue;
  473.     color->red = request->red;
  474.     color->green = request->green;
  475.     color->blue = request->blue;
  476.     XStoreColors(dpy, cmap, color, 1);
  477.     return 1;
  478. }
  479.  
  480.  
  481. /****************************************************************************/
  482. static int compare(e1, e2)
  483.     unsigned long    *e1, *e2;
  484. {
  485.     if (*e1 < *e2)    return -1;
  486.     if (*e1 > *e2)    return 1;
  487.     return 0;
  488. }
  489.  
  490.  
  491. /****************************************************************************/
  492. static Status readonly_map(dpy, vinfo, colormap)
  493.     Display        *dpy;
  494.     XVisualInfo        *vinfo;
  495.     XStandardColormap    *colormap;
  496. {
  497.     int            i, last_pixel;
  498.     XColor        color;
  499.  
  500.     last_pixel = (colormap->red_max + 1) * (colormap->green_max + 1) * 
  501.     (colormap->blue_max + 1) + colormap->base_pixel - 1;
  502.  
  503.     for(i=colormap->base_pixel; i <= last_pixel; i++) {
  504.  
  505.     color.pixel = (unsigned long) i;
  506.     color.red = (unsigned short)
  507.         (((i/colormap->red_mult) * 65535) / colormap->red_max);
  508.  
  509.     if (vinfo->class == StaticColor) {
  510.         color.green = (unsigned short)
  511.         ((((i/colormap->green_mult) % (colormap->green_max + 1)) *
  512.           65535) / colormap->green_max);
  513.         color.blue = (unsigned short)
  514.         (((i%colormap->green_mult) * 65535) / colormap->blue_max);
  515.     }
  516.     else    /* vinfo->class == GrayScale, old style allocation XXX */
  517.         color.green = color.blue = color.red;
  518.  
  519.     XAllocColor(dpy, colormap->colormap, &color);
  520.     if (color.pixel != (unsigned long) i)
  521.         return 0;
  522.     }
  523.     return 1;
  524. }
  525.